package main

import (
	"fmt"
	"reflect"
)

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) []int {
	if root == nil {
		return []int{} // 表示初始的是一个空的切片 等同于var a []int  a 此时等于nil
	}
	//	 建立辅助队列
	col := make([]*TreeNode, 0, 10)
	col = append(col, root)
	val := make([]int, 0, 10) // 结果值队列

	for len(col) != 0 {
		tmp := col[0] // 获取队列中的第一个值
		val = append(val, tmp.Val)
		if tmp.Left != nil { // 加入子队列
			col = append(col, tmp.Left)
		}
		if tmp.Right != nil { // 添加子队列
			col = append(col, tmp.Right)
		}
		col = col[1:] // 删除第一个元素
	}
	return val
}

// 修改打印的结果值;
// 同一行的放入到一个队列中
func levelOrder2(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{} // 表示初始的是一个空的切片 等同于var a []int  a 此时等于nil
	}
	//	 建立辅助队列
	res := make([][]int, 0)
	//col2 := make([]*TreeNode, 0)
	//col2 = 	append(col2, root)

	col2 := []*TreeNode{root} // 上面两行表示为一行
	for len(col2) != 0 {
		col := make([]*TreeNode, 0, 10)
		col = append(col, col2...) // 合并建立新的数组,原来的还是存在的。这里设计到底层的实现方式。
		val := make([]int, 0, 10)  // 这里需要建立新的空间给val 来使用,
		col2 = col2[:0]            // 清空的切片
		for len(col) != 0 {
			tmp := col[0] // 获取队列中的第一个值
			val = append(val, tmp.Val)
			if tmp.Left != nil { // 加入子队列
				col2 = append(col2, tmp.Left) //
			}
			if tmp.Right != nil { // 添加子队列
				col2 = append(col2, tmp.Right)
			}
			col = col[1:] // 删除第一个元素
		}
		res = append(res, val) // 给二维切片追加一维切片,如果需要合并的处理方式append([]int,[]int...) 添加三个点，表示解析
	}
	return res
}

// 之字型打印的二叉树
// 二叉树的打印三
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 修改打印的结果值;
// 同一行的放入到一个队列中
func levelOrder3(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{} // 表示初始的是一个空的切片 等同于var a []int  a 此时等于nil
	}
	//	 建立辅助队列
	res := make([][]int, 0)
	oct := 0
	//col2 := make([]*TreeNode, 0)
	//col2 = 	append(col2, root)
	col2 := []*TreeNode{root} // 上面两行表示为一行
	for len(col2) != 0 {
		col := make([]*TreeNode, 0, 10)
		col = append(col, col2...) // 合并建立新的数组,原来的还是存在的。这里设计到底层的实现方式。
		val := make([]int, 0, 10)  // 这里需要建立新的空间给val 来使用,
		col2 = col2[:0]            // 清空的切片
		oct++
		for len(col) != 0 {
			tmp := col[0] // 获取队列中的第一个值
			val = append(val, tmp.Val)
			if tmp.Left != nil { // 加入子队列
				col2 = append(col2, tmp.Left) //
			}
			if tmp.Right != nil { // 添加子队列
				col2 = append(col2, tmp.Right)
			}
			col = col[1:] // 删除第一个元素
		}
		if oct%2 == 0 {
			reverseAny(val)
		}
		res = append(res, val) // 给二维切片追加一维切片,如果需要合并的处理方式append([]int,[]int...) 添加三个点，表示解析
	}
	return res
}
func reverseAny(s interface{}) {
	n := reflect.ValueOf(s).Len()
	swap := reflect.Swapper(s)
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		swap(i, j)
	}
}

//	注意这一题目不是仅仅交换，第一数即可，同样它需要交互的是，局部的区域，同时需要整个读取顺序的颠倒；

func main() {
	l1 := &TreeNode{1, nil, nil}
	l2 := &TreeNode{2, nil, nil}
	l3 := &TreeNode{3, nil, nil}
	l4 := &TreeNode{4, nil, nil}
	l5 := &TreeNode{5, nil, nil}
	l1.Left = l2
	l1.Right = l3
	l3.Left = l4
	l3.Right = l5
	fmt.Println(levelOrder3(l1))
}

// 层序遍历
